# 数据格式: [[key,next,prev],...]
A=[['a',2,None],[None,4,None],['b',3,0],['c',5,2],\
   [None,6,1],['d',8,3],[None,7,4],[None,None,6],['e',None,5]]
L=0 #L,F are the heads
F=1
m=5

def compact_list(L): 
    idx=L
    for i in xrange(m):
        if A[i][0]==None:
            while A[idx][1]<m:
                idx=A[idx][1]
            idx=A[idx][1]
            A[i],A[idx]=A[idx],A[i]
            if A[i][1]!=None:
                A[A[i][1]][2]=i #fix next.prev
            if A[i][2]!=None:
                A[A[i][2]][1]=i #fix prev.next
            if A[idx][1]!=None:
                A[A[idx][1]][2]=idx
            if A[idx][2]!=None:
                A[A[idx][2]][1]=idx
            idx=i #idx已经移到i

if __name__=='__main__':
    print A
    compact_list(L)
    print A
    
